package com.duoduo.字符串;

import java.util.ArrayList;
import java.util.List;

/**
 * @author dl.chai
 * @version 1.0
 * @description: 括号生成22
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：["()"]
 * @date 2023/3/5 17:00
 */

public class 括号生成22 {
    public static void main(String[] args) {
        List<String> list = new 括号生成22().generateParenthesis(2);
        list.forEach(System.out::println);
    }
    List<String> result=new ArrayList<>();
    int n;
    public List<String> generateParenthesis(int n) {
        this.n = n;
        dfs("",0,0);
        return result;
    }
    public void dfs(String curr,int left,int right){
        //第一个就是做递归的退出条件  递归终止
        if (left==n && right == n){
            result.add(curr);
            return;
        }
        //剪枝
        if (left>n || left<right) {
            return;
        }
        dfs(curr+"(",left+1,right);
        dfs(curr+")",left,right+1);
    }
}
